package com.leetcodehot.problems;

public class problems357 {
    /**
     * 回溯问题最初版本的解法
     * 其实就是枚举 比如10000  后面4个0的位置 能够换还没出现的数字
     * 但是还得去除掉前导0，解决前导0使用count计数当前非0的个数
     */
    private int ans = 0;
    private int count = 0;

    public int countNumbersWithUniqueDigits(int n) {
        boolean[] col = new boolean[10];
        int[] path = new int[n];
        dfs(col, path, 0, n);
        return ans;
    }

    //枚举第i位
    private void dfs(boolean[] col, int[] path, int i, int n) {
        if (i == n) {
            ans++;
            return;
        }
        for (int j = 0; j < 10; j++) {
            if (!col[j] || count == 0) {
                count += j != 0 ? 1 : 0;
                col[j] = true;
                path[i] = j;
                dfs(col, path, i + 1, n);
                count -= j != 0 ? 1 : 0;
                col[j] = false;
            }
        }
    }
}
